​ICLR 2023 | 标识分支结点，提升图神经网络对环的计数能力

©作者 | 桑士龙

单位 | 南京邮电大学

来源 | MIND Laboratory

论文简介

信息传递网络 (Message Passing Neural Networks (MPNNs)) 表达能力的局限性促使着对更强大图神经网络 (Graph Neural Networks (GNNs)) 的研究。衡量某一GNN 模型表达能力更强的方法是其是否能更好地执行特殊的功能，比如对图中特定的子结构进行计数。对图中子结构计数这一任务对于生物化学、社交网络分析上的应用具有重要作用。 

基于此，本文对子图信息传递网络 (Subgraph MPNNs) 进行研究，证明了 Subgraph MPNNs 在结点水平上无法对多余 4 个结点组成的环进行计数。进而提出了 -GNNs，它通过对每个子图内根结点及在该子图内根节点的邻居结点赋予不同的标识符，实现对 subgraph MPNN 的拓展。

论文标题：

Boosting the Cycle Counting Power of Graph Neural Networks with I-GNNs

论文地址：

https://arxiv.org/pdf/2210.13978.pdf

-GNNs 被证明能够对所有 3、4、5、6 个结点组成的环进行计数，从而能够覆盖有机化学中类似苯环的大多数结构，与此同时保持线性复杂度。

研究动机

GNN 模型的表示能力可从两个角度进行评估：一是区分一组非同构图的能力，即 discriminative power。尽管这种评估方式能够对各种 GNN 模型进行比较，却无法得知这些模型能否执行某些具体函数。二是对 GNN 模型能执行的函数类别进行建模。本文认为图结构因与有机化学、生物学和社交网络分析的诸多任务有关，因此应当被重视。尤其是环状结构在有机化学中极其重要。因此，对像环这样的子结构进行估测的能力成为衡量模型表达能力的重要手段。 

ID-GNN 能被归类为一种子图神经网络 (Subgraph GNNs)，这是一类新的 GNN 模型，它的核心 idea 是将图分解为子图的集合，并通过对子图的表示进行聚合，得到整张图的表示。subgraph GNN 的表达能力严格强于 WL test，弱于 3-WL test。 

本文的主要贡献为：

1. 证明了 subgraph MPNN 在结点水平上能对 3 元环和 4 元环进行计数，却无法对更多元环进行计数；

2. 为克服这一局限，本文提出了 -GNNs，采用多重结点标识符对 subgraph MPNN 进行拓展。核心 idea 是由一个结点对生成子图，结点对由根节点和根节点的一个邻居结点组成。在新子图中赋予该结点对独特的标识符，本文认为这是提升模型表达能力的关键； 

3. 证明了 -GNNs 表达能力严格强于 WL test 和 subgraph MPNN，并在一定程度上强于 3-WL test。本文证明了 -GNNs 能够对组成结点数少于7的所有环进行计数。

方法

3.1 Preliminaries

本文主要研究对路径 (path) 和环 (cycle) 的计数，部分定义如下：

一个 L-path 被定义为一组边的序列 ，在其中，所有结点必须各不同的，也即 。

一个 L-cycle 是满足 的 -path。若两个 path 或cycle之间所包含的边的集合相同，则其被认为是等同的。 表示的是图 G 中对所有不等同子结构 S 的计数，S 可以是一个 -path 或 -cycle。

3.2 Counting power of MPNNs and Subgraph MPNNs

MPNN 是一类图神经网络，通过迭代地聚合邻居结点的信息，对目标结点的表示进行更新。

 表示结点 i 在迭代步 t 时的表示。MPNN 通过如下方式更新结点表示：

其中 和 表示所有结点之间共享的可学习函数。在 T 步后，最后的结点表示 被传递到一个 readout 函数中，输出图的表示：

然而 MPNN 的表达能力不佳，无法对长度超过 2 的环或路径进行计数。Subgraph GNN 通过一些预设定好的策略将图拆解为子图，并将子图表示聚图的表示。其采取的基于结点的策略如下：

分为子图的提取和对结点赋予标签。这里的表示一个指示函数。

采用 表示结点 j 在子图 i 中，第 t 个迭代步时的表示，Subgraph MPNN 在每个子图上遵循着以下的信息传递模型：

其中 表示在子图 中，结点 j 的邻居结点。类似地，在下步迭代后，结点 的表示 会通过一个结点水平的 readout 函数得出：

得到每个结点的表示后，再通过图水平的 readout 函数得到图表示：

Subgraph MPNN 相较 MPNN 更 powerful，原因是前者通过提取不含结点标签方法的 T-hop 网络来转化为 T 层 MPNN，以此来进行 T 层信息传递。本文概括了 Subgraph MPNN 在结点水平的计数能力：

3.3 -GNN

已知在子图中为根节点赋予独特的标识符能提升模型表达能力，进而猜测若赋予多个独特标识符又会如何，赋予哪些结点这样的标识符。 

由于 cycle 和 path 这样的子结构都是高度局部化的，基于这样的观察，应当采用一种局部的 labeling 方法：除子图根节点 i 之外，额外赋予另一个标识符给根节点的一个直接邻居结点，称其为分支节点 j (branching node j)，这样的操作每次对该根节点的一个邻居结点依次迭代进行。 

如图所示，首先提取出各结点的子图（图中是 2 阶导出子图），并为该结点赋予标识符，然后在一结点的子图中，分别为根节点的邻居结点赋予标识符，由此又产生了多个子图，在每个子图上进行子图级别的 MPNN，首先得到新子图中各结点的表示，通过边 readout 函数得到新子图中的分支结点的表示，得到每个分支节点的表示后再次进行结点 readout 函数，得到根节点i的表示，得到所有根节点表示后通过图 readout 函数得到图的表示。

本文认为 -GNN 得到性能提升的原因在于打破了根节点邻居的对称性。在由结点生成的子图 中，根节点 从不同分支节点处获取到的信息是不同的。

-GNN 的环计数能力被概括如下：

实验

在实验部分，聚焦三个问题：

4.1 Discriminating non-isomorphic graphs

探讨的是 discriminative power 问题，在区分非同构图上做实验。

4.2 Graph substructure counting

4.3 Molecular properties prediction

结论

本文提出通过模型对 cycle 和 path 的计数能力的角度对子图 MPNN 的表示能力进行研究。证明了子图 MPNN 在结点水平无法对超过 4 个结点组成的环进行计数，不利于其在化学生物领域的研究。

受环状结构的局部特性启发，本文提出了 -GNN，对根结点的邻居结点分别赋予独特标识符，经过多次聚合得到结点表示或图的表示，提升计数能力。-GNN 能够在线性时间内对至少 6 元环进行计数。

更多阅读

#投 稿 通 道#

 让你的文字被更多人看到 

如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。

总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 

PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个，让知识真正流动起来。

📝 稿件基本要求：

• 文章确系个人原创作品，未曾在公开渠道发表，如为其他平台已发表或待发表的文章，请明确标注 

• 稿件建议以 markdown 格式撰写，文中配图以附件形式发送，要求图片清晰，无版权问题

• PaperWeekly 尊重原作者署名权，并将为每篇被采纳的原创首发稿件，提供业内具有竞争力稿酬，具体依据文章阅读量和文章质量阶梯制结算

📬 投稿通道：

• 投稿邮箱：[e-mail] 

• 来稿请备注即时联系方式（微信），以便我们在稿件选用的第一时间联系作者

• 您也可以直接添加小编微信（pwbot02）快速投稿，备注：姓名-投稿

△长按添加PaperWeekly小编

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧

·